/LMAR=0/XLINE=3/FONT#0=BASL30/FONT#1=BASI30/FONT#2=BASB30



␈↓ α∧␈↓␈↓ α⊂DISPLAY GENERATED BY A GENERALIZED CONE REPRESENTATION

␈↓ α∧␈↓Eiichi␈α Miyamoto:␈α Department␈αof␈α Information␈α Engineering,␈α Hokkaido␈α
University,
␈↓ α∧␈↓Sapporo, Japan.

␈↓ α∧␈↓Thomas␈α∪ O.␈α∪  Binford:␈α∀ Arti≡cial␈α∪ Intelligence␈α∪ Laboratory,␈α∀Stanford␈α∪University,
␈↓ α∧␈↓Stanford, Calif, 94305.



␈↓ α∧␈↓␈↓ ∧s␈↓&ABSTRACT␈↓)αβ

␈↓ α∧␈↓We␈α∂ describe␈α∞ the␈α∂ generalized␈α∞ cone␈α∂ representation␈α∞ and␈α∂  its␈α∞ data
␈↓ α∧␈↓structure␈α⊃ for␈α⊃ a␈α⊃ class␈α⊂ of␈α⊃three-dimensional␈α⊃ curved␈α⊃ objects,␈α⊂ and
␈↓ α∧␈↓describe␈α∞ an␈α∞ algorithm␈α∞for␈α
 hidden␈α∞ line␈α∞elimination␈α∞ for␈α
displaying
␈↓ α∧␈↓objects.␈α∪  In␈α∪ the␈α∪ generalized␈α∪ cone␈α∪representation,␈α∪ an␈α∪ object␈α∩ is
␈↓ α∧␈↓represented␈α∪by␈α∪a␈α∪ sequence␈α∪of␈α∪disjoint␈α∪slices␈α∪called␈α∪cross␈α∪sections,
␈↓ α∧␈↓normal␈α to␈αa␈αspace␈αcurve␈αcalled␈αthe␈αspine.␈α  Accordingly,␈α an␈αobject␈αis
␈↓ α∧␈↓displayed␈α⊂with␈α⊂ cross␈α⊂section␈α∂ edges␈α⊂and␈α⊂ longitudinal␈α⊂ edges␈α∂which
␈↓ α∧␈↓connect␈α≥ corresponding␈α≥points␈α≥of␈α≥two␈α≥adjacent␈α≥cross␈α≥sections.
␈↓ α∧␈↓Modelling by generalized cones simpli≡es input for curved objects.

␈↓ α∧␈↓ The␈α∂program␈α∂ ≡rst␈α∂suppresses␈α∂hidden␈α∞lines␈α∂within␈α∂ a␈α∂segment␈α∂of␈α∞a
␈↓ α∧␈↓part,␈α∩between␈α∩two␈α∩adjacent␈α∩cross␈α∩sections.␈α∩ Lines␈α∩hidden␈α∪by␈α∩other
␈↓ α∧␈↓segments␈α
of␈α
parts␈αare␈α
eliminated␈α
by␈α
a␈αbrute␈α
force␈α
comparison␈α
of␈αone
␈↓ α∧␈↓segment versus every other segment.


␈↓ α∧␈↓␈↓ ∧J␈↓&INTRODUCTION␈↓)αβ

␈↓ α∧␈↓We␈α⊂  require␈α⊂  that␈α⊂  a␈α⊂  representation␈α⊂  give␈α⊃  simple␈α⊂  part/whole
␈↓ α∧␈↓decompositions␈α
for␈α
familiar␈α
objects,␈α
 decompositions␈α
which␈α
correspond
␈↓ α∧␈↓to␈α⊂ our␈α⊃intuitive␈α⊂ sense␈α⊃of␈α⊂ parts.␈α⊃  Like␈α⊂ most␈α⊃representations,␈α⊂ the
␈↓ α∧␈↓Generalized␈α
Cone␈αrepresentation␈α
 is␈αa␈α
part/whole␈α graph␈α
of␈αan␈α
 object
␈↓ α∧␈↓structured␈α
 into␈α
parts␈α
 by␈α
 cutting␈α
 and␈α
pasting.␈α
 The␈α
 parts␈α∞may␈α
 be
␈↓ α∧␈↓structured␈α
 into␈α
 subparts␈α
 to␈α
 any␈α
 depth.␈α
   The␈α
di≥erence␈α between
␈↓ α∧␈↓representations␈α∞is␈α∞ the␈α∞choice␈α∞ of␈α∞primitives␈α∞and␈α∞ the␈α∞process␈α∞ which
␈↓ α∧␈↓generates␈α⊂ descriptions␈α⊂of␈α⊂ objects␈α⊂within␈α⊂ the␈α⊃representation.␈α⊂  The
␈↓ α∧␈↓design␈αcriteria␈αfor␈αgeneralized␈αcone␈αprimitives␈αare:␈αa)␈αparts␈α should␈α
be
␈↓ α∧␈↓de≡ned␈α∩by␈α∩continuity;␈α∩b)␈α∩parts␈α∩should␈α∩correspond␈α∩to␈α∩our␈α⊃intuitive
␈↓ α∧␈↓notion␈α of␈αparts;␈αc)␈α parts␈αwhich␈αwe␈α regard␈αas␈αsimilar␈α should␈αhave␈αa
␈↓ α∧␈↓simple␈α⊃sense␈α⊃ of␈α⊃similarity␈α⊃ in␈α⊃the␈α⊃ representation;␈α⊃d)␈α⊂ relationships
␈↓ α∧␈↓which␈α∞we␈α∞regard␈α∞ as␈α∞signi≡cant␈α∞for␈α∞shape␈α∞description,␈α∞ such␈α∞as␈α
thin,
␈↓ α∧␈↓should␈α⊂be␈α⊃explicit.␈α⊂ These␈α⊃criteria␈α⊂imply␈α⊃that␈α⊂primitives␈α⊃should␈α⊂be
␈↓ α∧␈↓volumes␈αrather␈αthan␈αsurfaces.␈α Most␈αpeople␈αregard␈αa␈αblock␈αas␈αa␈αsingle
␈↓ α∧␈↓part,␈α∞rather␈α∞than␈α∞as␈α∞six␈α∞surface␈α
parts.␈α∞ That␈α∞is,␈α∞we␈α∞don't␈α∞segment␈α
at
␈↓ α∧␈↓surface␈α∂discontinuity.␈α∂  Further,␈α⊂parts␈α∂should␈α∂be␈α∂generated␈α⊂ by␈α∂local
␈↓ α∧␈↓volumes;␈α∩  our␈α∩ intuitive␈α∩ segmentations␈α⊃  require␈α∩ a␈α∩  rich␈α∩ set␈α⊃ of
␈↓ α∧␈↓primitives.␈α We␈α want␈αthe␈αlocal␈α volumes␈αto␈αbe␈α disjoint␈αfor␈αour␈α own
␈↓ α∧␈↓convenience␈α⊃ in␈α⊃ visualizing.␈α⊃   Thus,␈α⊃we␈α⊃ seek␈α⊃ volume␈α⊃ primitives
␈↓ α∧␈↓de≡ned␈α
by␈α
 continuity.␈α
 Generalized␈α
cone␈α
primitives␈α
are␈α
de≡ned␈α
by␈αa
␈↓ α∧␈↓sequence␈α
of␈α
thin␈α
slices␈α
normal␈α
to␈α
some␈α
space␈α
curve␈α
 called␈α
the␈α
spine.
␈↓ α∧␈↓The␈α slices␈αcan␈α be␈αdescribed␈α by␈αa␈α continuous␈αfunction␈α(whose␈αvalue
␈↓ α∧␈↓is␈α
a␈α
cross␈α
section)␈α
along␈α
 the␈α
 spine.␈α
   The␈α
 representation␈α
 is␈α based
␈↓ α∧␈↓on␈α⊗the␈α↔"generalized␈α⊗translational␈α↔invariance"␈α⊗formalism.␈α↔ In␈α⊗this
␈↓ α∧␈↓formalism,␈αnormal␈αcross␈αsections␈α are␈αmapped␈αinto␈αother␈αnormal␈αcross
␈↓ α∧␈↓sections␈α∂by␈α∂translation␈α∂followed␈α∂by␈α∂some␈α∂congruence␈α∂transformation.



␈↓ α∧␈↓For␈α
example,␈α
a␈α
cylinder␈α
is␈α
de≡ned␈α
by␈α
any␈α
plane␈α
≡gure␈α
translated␈α
along
␈↓ α∧␈↓a␈α
straight␈α∞line.␈α
  A␈α∞ cone␈α
is␈α∞ de≡ned␈α
by␈α∞ any␈α
plane␈α∞ ≡gure␈α
translated
␈↓ α∧␈↓along␈αa␈αstraight␈αline,␈α with␈αa␈α scaling␈αfunction␈α which␈αis␈α linear␈αalong
␈↓ α∧␈↓the line.

␈↓ α∧␈↓The␈α
representation␈α
 of␈α
 cross␈α∞sections␈α
 is␈α
the␈α
 same␈α
 problem␈α∞in␈α
 two
␈↓ α∧␈↓dimensions.␈α∂  The␈α∂ representation␈α∂of␈α∂cross␈α∂ sections␈α∂is␈α∂ a␈α∂part/whole
␈↓ α∧␈↓representation,␈α∞with␈α∞area␈α∞primitives␈α∞(not␈α∞curve␈α∞primitives)␈α
connected
␈↓ α∧␈↓by␈αcutting␈αand␈αpasting.␈α The␈αprimitives␈αare␈αformalized␈αby␈α
generalized
␈↓ α∧␈↓translational␈α
 invariance␈α
in␈α
two␈α
dimensions,␈α
expressed␈α
 in␈α
terms␈α
of␈αa
␈↓ α∧␈↓plane␈α
curve␈α∞called␈α
the␈α∞spine,␈α
and␈α∞straight␈α
lines␈α∞normal␈α
 to␈α∞the␈α
spine
␈↓ α∧␈↓(cross sections of one-dimension).

␈↓ α∧␈↓The␈α
representation␈α has␈α
been␈αused␈α
 in␈αscene␈α
analysis␈α
 for␈αdescription
␈↓ α∧␈↓and␈α
 recognition␈α
  of␈α
  curved␈α
  objects␈α
 [1,2].␈α
     The␈αrepresentation
␈↓ α∧␈↓best␈α⊃describes␈α⊃ parts␈α⊃with␈α⊃ cross␈α⊃ sections␈α⊃ which␈α⊃ change␈α⊃smoothly
␈↓ α∧␈↓along some space curve.


␈↓ α∧␈↓␈↓ αO␈↓&DATA STRUCTURE FOR THE REPRESENTATION␈↓)αβ

␈↓ α∧␈↓In␈α⊂ the␈α∂ program,␈α⊂ parts␈α∂are␈α⊂ described␈α∂ as␈α⊂ interpolation␈α∂ functions
␈↓ α∧␈↓(splines)␈α∂ for␈α∂samples␈α∂of␈α∂cross␈α∂ sections␈α∂normal␈α∂to␈α∂the␈α∂ spine.␈α∂ Thus
␈↓ α∧␈↓parts␈α⊂are␈α⊂ represented␈α⊂as␈α⊃ sequences␈α⊂of␈α⊂ cross␈α⊂sections.␈α⊃  The␈α⊂ cross
␈↓ α∧␈↓sections␈α∂are␈α∂described␈α∞in␈α∂curve␈α∂ form,␈α∞as␈α∂interpolation␈α∂functions␈α∞for
␈↓ α∧␈↓curve␈α
samples.␈α
 Cross␈α
sections␈α
may␈αbe␈α
circles␈α
or␈α
combinations␈α
of␈αline
␈↓ α∧␈↓segments␈α∂and␈α⊂ arcs.␈α∂  That␈α⊂ representation␈α∂for␈α⊂ cross␈α∂sections␈α⊂ is␈α∂an
␈↓ α∧␈↓expedient;␈α∀ it␈α∪ is␈α∀inconsistent␈α∪ with␈α∀ the␈α∪ representation␈α∀for␈α∪ cross
␈↓ α∧␈↓sections␈α∂ described␈α∞ above.␈α∂   There␈α∂ are␈α∞ cross␈α∂ section␈α∂  edges␈α∞ and
␈↓ α∧␈↓longitudinal␈α∂ edges␈α⊂ which␈α∂ tie␈α⊂ together␈α∂  corresponding␈α⊂ points␈α∂ of
␈↓ α∧␈↓adjacent␈α∞cross␈α∂ sections␈α∞(see␈α∂≡gure␈α∞1).␈α∞ Although␈α∂arcs␈α∞ or␈α∂curves␈α∞are
␈↓ α∧␈↓now␈α∩displayed␈α∩as␈α∩line␈α∪segments,␈α∩the␈α∩display␈α∩of␈α∪longitudinal␈α∩edges
␈↓ α∧␈↓connecting␈α∃points␈α∃on␈α∀arcs␈α∃may␈α∃be␈α∀suppressed,␈α∃because␈α∃these␈α∀are
␈↓ α∧␈↓artifacts.

␈↓ α∧␈↓Each␈α∞sample␈α∞ point␈α∞along␈α∞a␈α∞ cross␈α∞section␈α∞ is␈α∞speci≡ed␈α∞by␈α
 Cartesian
␈↓ α∧␈↓coordinates␈α⊂ in␈α⊂ the␈α⊂sense␈α⊂ of␈α⊃ a␈α⊂ right␈α⊂screw␈α⊂ in␈α⊂ the␈α⊃ direction␈α⊂of
␈↓ α∧␈↓generation␈α⊃of␈α⊃ the␈α⊃object␈α⊃ (in␈α⊃the␈α⊃ order␈α⊃of␈α⊃ cross␈α∩ section).␈α⊃  This
␈↓ α∧␈↓ordering␈α∞determines␈α
the␈α∞interior␈α
of␈α∞the␈α
object.␈α∞ Each␈α
point␈α∞lies␈α∞on␈α
a
␈↓ α∧␈↓cross␈α∃section␈α∃edge␈α∀and␈α∃a␈α∃longitudinal␈α∀edge.␈α∃ Each␈α∃edge␈α∃may␈α∀be
␈↓ α∧␈↓divided␈α↔into␈α↔an␈α↔arbitrary␈α↔number␈α↔of␈α↔segments␈α↔by␈α_hidden␈α↔line
␈↓ α∧␈↓elimination.

␈↓ α∧␈↓Each␈αobject␈αhas␈αits␈αown␈α coordinate␈αsystem␈αand␈αa␈αrelationship␈α to␈αthe
␈↓ α∧␈↓coordinate␈αsystem␈αof␈αa␈αparent␈α object␈αor␈αof␈αthe␈αworld.␈α Objects␈αwhich
␈↓ α∧␈↓have␈α⊂the␈α∂ same␈α⊂parent␈α⊂ are␈α∂ called␈α⊂siblings.␈α∂   There␈α⊂exists␈α⊂ a␈α∂ tree
␈↓ α∧␈↓structure among objects.



␈↓ α∧␈↓When␈α∂ objects␈α⊂ are␈α∂  displayed,␈α∂ their␈α⊂ local␈α∂ coordinates␈α⊂  must␈α∂ be
␈↓ α∧␈↓transformed␈α⊂ into␈α⊃ world␈α⊂coordinates.␈α⊂   Let␈α⊃T␈↓#vi␈↓#␈α⊂ be␈α⊃ the␈α⊂translation
␈↓ α∧␈↓vector␈α∞and␈α∞let␈α∞R␈↓#vi␈↓#␈α∞be␈α
 the␈α∞rotation␈α∞matrix␈α∞for␈α∞transformation␈α∞of␈α
 the
␈↓ α∧␈↓i␈↓#
th␈↓#␈α∞child␈α
 to␈α∞world␈α
coordinates.␈α∞  Then␈α
we␈α∞can␈α
set␈α∞ up␈α∞the␈α
following
␈↓ α∧␈↓relations:
␈↓ α∧␈↓    T␈↓#vi␈↓# = T␈↓#vi-1␈↓#+ R␈↓#vi-1␈↓#t␈↓#vi-1,i␈↓#,
␈↓ α∧␈↓    R␈↓#vi␈↓# = R␈↓#vi-1␈↓#r␈↓#vi-1,i␈↓#,

␈↓ α∧␈↓where␈αT␈↓#v0␈↓#␈α is␈αthe␈α
zero␈αvector␈αand␈α where␈α
R␈↓#v0␈↓#␈αis␈αthe␈αunit␈αmatrix.␈α
 Here,
␈↓ α∧␈↓t␈↓#vi-1,i␈↓#␈α∞  =␈α∞  (x␈↓#vi-1,i␈↓#,y␈↓#vi-1,i␈↓#,z␈↓#vi-1,i␈↓#)␈↓#
T␈↓#␈α∞   is␈α∞  the␈α∞translation␈α∞ vector␈α∞from␈α
 the
␈↓ α∧␈↓i␈↓#
th␈↓#  child  coordinate frame  to its parent's frame, and
␈↓ α∧␈↓                        i␈↓#vx␈↓#  j␈↓#vx␈↓#  k␈↓#vx␈↓#
␈↓ α∧␈↓        r␈↓#vi-1,i␈↓# =       i␈↓#vy␈↓#  j␈↓#vy␈↓#  k␈↓#vy␈↓#
␈↓ α∧␈↓                        i␈↓#vz␈↓#  j␈↓#vz␈↓#  k␈↓#vz␈↓#

␈↓ α∧␈↓is␈α
the␈α
rotation␈α
matrix␈α
from␈α
the␈αcoordinate␈α
 frame␈α
of␈α
the␈α
i␈↓#
th␈↓#␈α
child␈αto
␈↓ α∧␈↓its␈α
 parent's␈α
frame.␈α
 The␈α
rotation␈α
 can␈α
be␈α
speci≡ed␈α
by␈α
a␈αrotation␈α
vector
␈↓ α∧␈↓for␈α∞which␈α
the␈α∞ direction␈α
of␈α∞the␈α
 vector␈α∞speci≡es␈α
the␈α∞axis␈α∞ of␈α
rotation
␈↓ α∧␈↓and␈αthe␈α magnitude␈αof␈α the␈α vector␈αspeci≡es␈α the␈αangle␈α of␈αrotation␈αin
␈↓ α∧␈↓radians.␈α∩ Given␈α∩such␈α∩a␈α∩rotation␈α∩vector␈α∩w␈↓#vx␈↓#,␈α∩w␈↓#vy␈↓#,␈α∩w␈↓#vz␈↓#␈α∩with␈α⊃direction
␈↓ α∧␈↓cosines␈α∂c␈↓#vx␈↓#,␈α∂c␈↓#vy␈↓#,␈α∞c␈↓#vz␈↓#␈α∂and␈α∂magnitude␈α∞W␈α∂in␈α∂ radians.␈α∞ Let␈α∂c␈↓#vw␈↓#␈α∂be␈α∞cos(W)
␈↓ α∧␈↓and␈αs␈↓#vw␈↓#␈α
be␈αsin(W).␈α
  Then␈αthe␈α
relation␈α between␈α
a␈αrotation␈αmatrix␈α
and
␈↓ α∧␈↓a rotation vector [3] is as follows:
␈↓ α∧␈↓        i␈↓#vx␈↓# = (1-c␈↓#vw␈↓#)c␈↓#vx␈↓#c␈↓#vy␈↓# + c␈↓#vw␈↓#
␈↓ α∧␈↓        j␈↓#vx␈↓# = (1-c␈↓#vw␈↓#)c␈↓#vx␈↓#c␈↓#vy␈↓# + c␈↓#vz␈↓#s␈↓#vw␈↓#
␈↓ α∧␈↓        k␈↓#vx␈↓# = (1-c␈↓#vw␈↓#)c␈↓#vx␈↓#c␈↓#vz␈↓# + c␈↓#vy␈↓#s␈↓#vw␈↓#
␈↓ α∧␈↓        i␈↓#vy␈↓# = (1-c␈↓#vw␈↓#)c␈↓#vy␈↓#c␈↓#vx␈↓# + c␈↓#vz␈↓#s␈↓#vw␈↓#
␈↓ α∧␈↓        j␈↓#vy␈↓# = (1-c␈↓#vw␈↓#)c␈↓#vy␈↓#c␈↓#vy␈↓# + c␈↓#vw␈↓#
␈↓ α∧␈↓        k␈↓#vy␈↓# = (1-c␈↓#vw␈↓#)c␈↓#vy␈↓#c␈↓#vz␈↓# - c␈↓#vx␈↓#s␈↓#vw␈↓#
␈↓ α∧␈↓        i␈↓#vz␈↓# = (1-c␈↓#vw␈↓#)c␈↓#vz␈↓#c␈↓#vx␈↓# - c␈↓#vy␈↓#s␈↓#vw␈↓#
␈↓ α∧␈↓        j␈↓#vz␈↓# = (1-c␈↓#vw␈↓#)c␈↓#vz␈↓#c␈↓#vy␈↓# + c␈↓#vx␈↓#s␈↓#vw␈↓#
␈↓ α∧␈↓        k␈↓#vz␈↓# = (1-c␈↓#vw␈↓#)c␈↓#vz␈↓#c␈↓#vz␈↓# + c␈↓#vw␈↓#  .

␈↓ α∧␈↓The␈αscreen␈αis␈αchosen␈αas␈αthe␈α
plane␈αz␈α=␈α 0,␈αand␈αthe␈αobserver␈α
is␈αlocated
␈↓ α∧␈↓at␈α∂ the␈α∞point␈α∂(0,0,c),␈α∂in␈α∞ the␈α∂world␈α∂coordinates,␈α∞where␈α∂ c>0.␈α∂ Then␈α∞a
␈↓ α∧␈↓point␈α∃ (x,y,z)␈α∃  in␈α∃  world␈α∀ coordinates␈α∃  projects␈α∃ to␈α∃  the␈α∀  point
␈↓ α∧␈↓(cx/(c-x),cy/(c-y)) on the screen.



␈↓ α∧␈↓␈↓ βn␈↓&HIDDEN LINE ELIMINATION␈↓)αβ

␈↓ α∧␈↓Let␈αus␈αde≡ne␈αa␈αpiece␈αas␈αthe␈αvolume␈αbetween␈α a␈αpair␈αof␈αadjacent␈αcross
␈↓ α∧␈↓sections.␈α∩ First,␈α⊃ lines␈α∩within␈α⊃a␈α∩piece␈α⊃are␈α∩eliminated␈α⊃as␈α∩follows.␈α⊃ A
␈↓ α∧␈↓surface␈α⊃is␈α⊂ visible␈α⊃ if␈α⊂the␈α⊃ normal␈α⊂to␈α⊃ the␈α⊂ surface␈α⊃has␈α⊃ a␈α⊂ positive
␈↓ α∧␈↓component␈α∞ along␈α
the␈α∞ ray␈α
to␈α∞ the␈α
observer.␈α∞  An␈α
 edge␈α∞is␈α∞ visible␈α
if
␈↓ α∧␈↓either␈α⊂ surface␈α⊂is␈α⊂ visible␈α⊂ at␈α⊂the␈α⊂ edge.␈α⊂  Because␈α⊂of␈α⊂ the␈α⊂sense␈α∂ of
␈↓ α∧␈↓ordering␈α
of␈α
cross␈α
sections,␈α
the␈α
≡rst␈α
cross␈α
section␈α
is␈α
visible␈α
if␈α
its␈α
edges
␈↓ α∧␈↓have␈αa␈αclockwise␈α
 sense␈αon␈α the␈αscreen,␈α
 and␈αthe␈α second␈α
cross␈αsection
␈↓ α∧␈↓is␈αvisible␈αif␈αits␈αedges␈αhave␈αa␈αcounterclockwise␈αsense␈αon␈α the␈αscreen.␈α If
␈↓ α∧␈↓the␈αcross␈α
section␈αis␈α
convex,␈αthe␈α
angle␈αbetween␈α
successive␈αedges␈α will␈α
be
␈↓ α∧␈↓less␈α≤than␈α≠ pi␈α≤for␈α≠clockwise␈α≤image,␈α≠ and␈α≤greaer␈α≠than␈α≤pi␈α≠for
␈↓ α∧␈↓counterclockwise␈α≠image.␈α≠   However,␈α≠ if␈α≠ the␈α≠ cross␈α≠ section␈α≠ is
␈↓ α∧␈↓nonconvex,␈αthe␈αsum␈α of␈αangles␈αbetween␈αsuccessive␈αedges␈αwill␈α be␈α2π␈αif
␈↓ α∧␈↓clockwise and -2π if negative.

␈↓ α∧␈↓A␈α∂ longitudinal␈α∂plane␈α∂is␈α∂ visible␈α∂if␈α∂ the␈α∂angle␈α∂from␈α∂ a␈α⊂cross␈α∂section
␈↓ α∧␈↓edge␈α⊃of␈α⊃ the␈α∩≡rst␈α⊃ cross␈α⊃section␈α⊃ to␈α∩ the␈α⊃longitudinal␈α⊃ edge␈α∩in␈α⊃ the
␈↓ α∧␈↓counterclockwise␈α∪sense␈α∪ is␈α∪less␈α∪than␈α∪π.␈α∪    At␈α∪ concavities␈α∀in␈α∪cross
␈↓ α∧␈↓sections,␈α∂invisible␈α∞ longitudinal␈α∂ planes␈α∞may␈α∂ hide␈α∞ planes␈α∂visible␈α∞by
␈↓ α∧␈↓the␈α∀ above␈α∀condition␈α∀ (≡gure␈α∃2).␈α∀ That␈α∀ portion␈α∀of␈α∃ the␈α∀partially
␈↓ α∧␈↓visible␈α∩ plane␈α∩ which␈α∩ overlaps␈α⊃ the␈α∩ invisible␈α∩ plane␈α∩ is␈α⊃obscured.
␈↓ α∧␈↓The␈α∞results␈α∞for␈α∞this␈α∞stage␈α∞are␈α∞shown␈α∞in␈α∞≡gure␈α∞3␈α∞for␈α∞the␈α∂example␈α∞in
␈↓ α∧␈↓≡gure 1.

␈↓ α∧␈↓The␈α
contour␈αedges␈α
 of␈αa␈α
piece␈αare␈α
 those␈αwith␈α
one␈αvisible␈α
 surface␈αat
␈↓ α∧␈↓the␈α∀ edge.␈α∪   At␈α∀ concavities␈α∪ in␈α∀ the␈α∪ cross␈α∀ section,␈α∀ portions␈α∪ of
␈↓ α∧␈↓longitudinal edges are interior to  the contour of the piece  (≡gure 2).

␈↓ α∧␈↓To␈αeliminate␈αedges␈α obscured␈αby␈α
other␈αpieces,␈αeach␈α piece␈αis␈α
compared
␈↓ α∧␈↓with␈α∞ every␈α∞ other␈α∂ piece.␈α∞   Bounding␈α∞ rectangles␈α∞ aligned␈α∂with␈α∞ the
␈↓ α∧␈↓coordinate␈α
axes␈α
of␈α
the␈α
screen␈αare␈α
calculated,␈α
and␈α
 those␈α
pieces␈αwhose
␈↓ α∧␈↓bounding␈α
rectangles␈α are␈α
disjoint␈α
are␈α immediately␈α
ignored.␈α
  For␈αthe
␈↓ α∧␈↓rest,␈α⊂for␈α⊂ each␈α⊂edge␈α⊂ on␈α⊂ the␈α⊃contour␈α⊂ of␈α⊂a␈α⊂ piece,␈α⊂ if␈α⊂there␈α⊃ is␈α⊂ an
␈↓ α∧␈↓apparent␈α∞intersection␈α
with␈α∞ edges␈α
of␈α∞the␈α
 contour␈α∞of␈α
the␈α∞ other␈α
piece
␈↓ α∧␈↓(within␈α the␈αline␈αintervals),␈αit␈α is␈αdetermined␈αwhich␈α line␈αis␈αnearer␈αthe
␈↓ α∧␈↓observer at the apparent intersection.

␈↓ α∧␈↓In␈α∞cases␈α∞in␈α∞which␈α
the␈α∞projection␈α∞of␈α∞an␈α
object␈α∞is␈α∞entirely␈α∞ within␈α
the
␈↓ α∧␈↓projection␈α∞of␈α∂another␈α∞object,␈α∂there␈α∞is␈α∂no␈α∞intersection.␈α∂ To␈α∞determine
␈↓ α∧␈↓this␈α∂ case,␈α∂the␈α∂ apparent␈α∂intersections␈α∞ of␈α∂an␈α∂ extended␈α∂edge␈α∂ of␈α∞the
␈↓ α∧␈↓contour␈αof␈αone␈αpiece␈αwith␈α
 the␈αcontour␈αof␈αthe␈αother␈αpiece␈α
 are␈αfound.
␈↓ α∧␈↓If␈α⊃ two␈α⊃intersections␈α⊃are␈α⊃ found␈α⊃on␈α⊃ di≥erent␈α⊃sides␈α⊃ of␈α⊃the␈α⊃ line,␈α⊂a
␈↓ α∧␈↓hypothetical␈α∞line␈α∂is␈α∞considered␈α∞between␈α∂the␈α∞two␈α∞intersections␈α∂for␈α∞the
␈↓ α∧␈↓larger␈α∂piece,␈α∞and␈α∂it␈α∞is␈α∂decided␈α∂which␈α∞edge␈α∂is␈α∞nearer.␈α∂ This␈α∂fails␈α∞for
␈↓ α∧␈↓some␈α∂ nonconvex␈α∂ pieces.␈α∂   If␈α∂ the␈α∂ projections␈α∂ of␈α∂ the␈α∂ pieces␈α∞ are
␈↓ α∧␈↓disjoint, the two intersections fall on the same side of the line.



␈↓ α∧␈↓After␈αthe␈αdecision␈αof␈α which␈αpiece␈αis␈α closer,␈αevery␈αvisible␈αline␈α of␈αthe
␈↓ α∧␈↓further␈α⊃ piece␈α⊂is␈α⊃ checked␈α⊂to␈α⊃remove␈α⊂ the␈α⊃hidden␈α⊃ portion␈α⊂between
␈↓ α∧␈↓apparent␈α∂ crossing␈α∂points␈α∂with␈α∂ the␈α∂contour␈α∂of␈α∂ the␈α∂occluding␈α∂piece.
␈↓ α∧␈↓Figures␈α∪4␈α∪and␈α∪5␈α∪demonstrate␈α∪complex␈α∪objects␈α∪after␈α∪execution␈α∪ of
␈↓ α∧␈↓hidden line elimination.


␈↓ α∧␈↓␈↓ ∧`␈↓&CONCLUSION␈↓)αβ

␈↓ α∧␈↓The␈α∞representation␈α∞of␈α∞an␈α∞ object␈α∞by␈α∞disjoint␈α∞slices␈α∞is␈α∂convenient␈α∞for
␈↓ α∧␈↓use␈α∂in␈α∞ vision␈α∂and␈α∞ planning␈α∂for␈α∞ manipulation.␈α∂  In␈α∞this␈α∂ case,␈α∞ the
␈↓ α∧␈↓primary␈αadvantages␈αare␈αease␈αof␈αinput,␈αdisplay␈α of␈αcurved␈αobjects␈αwith
␈↓ α∧␈↓no␈αartifact␈αedges,␈α and␈αcompact␈αdata␈αstructure.␈α The␈αprogram␈αis␈αbeing
␈↓ α∧␈↓extended␈α∞ to␈α∂  adequately␈α∞ deal␈α∞  with␈α∂ hollow␈α∞  objects␈α∂ and␈α∞  other
␈↓ α∧␈↓nonconvexities.

␈↓ α∧␈↓References:

␈↓ α∧␈↓1)␈α
R.K.Nevatia,"Structured␈α
Descriptions␈α
of␈α
Complex␈α
Curved␈α
Objects
␈↓ α∧␈↓for␈α
Recognition␈α
and␈α
Visual␈α
Memory",␈α
Stanford␈α∞Arti≡cial␈α
Intelligence
␈↓ α∧␈↓Laboratory Memo AIM-250, October 1974.

␈↓ α∧␈↓2)␈α∃G.J.Agin,"Representation␈α∃and␈α∃Description␈α∃of␈α⊗Curved␈α∃Objects",
␈↓ α∧␈↓Stanford␈α∂Arti≡cial␈α∂Intelligence␈α∞Laboratory␈α∂Memo␈α∂AIM-173,␈α∞October
␈↓ α∧␈↓1972.

␈↓ α∧␈↓3)␈α
Bruce␈α
 G.␈αBaumgart;␈α
 "Geometric␈α
Modeling␈α
 for␈αComputer␈α
Vision";
␈↓ α∧␈↓Stanford␈αArti≡cial␈α
Intelligence␈α Laboratory,␈α
Memo␈αAIM-249,␈α
Stanford
␈↓ α∧␈↓University, October 1974.